package com.zjsru.oneDay202204;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @Author: likew
 * @Date: 2022/4/28
 *
 * 太平洋大西洋水流问题
 * 如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
 * 输入: heights = [[1,2,2,3,5],
 *                [3,2,3,4,4],
 *                [2,4,5,3,1],
 *                [6,7,1,4,5],
 *                [5,1,1,2,4]]
 * 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
 *
 */
public class pacificAtlantic {
    int n, m;
    int[][] g;
    /**BFS*/
//    public List<List<Integer>> pacificAtlantic(int[][] heights) {
//        g = heights;
//        m = g.length;n=g[0].length;
//        Deque<int[]> d1 = new ArrayDeque<>(),d2 = new ArrayDeque<>();
//        boolean[][] res1 = new boolean[m][n],res2 = new boolean[m][n];
//        for(int i=0;i < m;i++){
//            for (int j = 0; j < n; j++) {
//                if(i==0 || j==0){
//                    res1[i][j] = true;
//                    d1.addLast(new int[]{i,j});
//                }
//                if(i ==m-1 || j==n-1){
//                    res2[i][j] = true;
//                    d2.addLast(new int[]{i,j});
//                }
//            }
//        }
//        bfs(d1,res1);
//        bfs(d2,res2);
//        List<List<Integer>> ans = new ArrayList<>();
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if(res1[i][j] && res2[i][j]){
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i);
//                    list.add(j);
//                    ans.add(list);
//                }
//            }
//        }
//        return ans;
//    }
//    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//    void bfs(Deque<int[]> d,boolean[][] res){
//        while(!d.isEmpty()){
//            int[] info = d.pollFirst();
//            int x = info[0],y =info[1],t=g[x][y];
//            for(int[] di : dirs){
//                int nx =x + di[0],ny= y+di[1];
//                if(nx<0 || nx >= m || ny <0 || ny>=n) continue;
//                if(res[nx][ny] || g[nx][ny]<t) continue;
//                d.addLast(new int[]{nx,ny});
//                res[nx][ny] = true;
//            }
//        }
//    }
    
    /**DFS*/
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        g = heights;
        m = g.length; n = g[0].length;
        boolean[][] res1 = new boolean[m][n],res2 = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i == 0 || j == 0){
                    if(!res1[i][j]) dfs(i,j,res1);
                }
                if(i == m-1 || j == n-1){
                    if(!res2[i][j]) dfs(i,j,res2);
                }
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(res1[i][j] && res2[i][j]){
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    void dfs(int x,int y,boolean[][] res){
        res[x][y] = true;
        for (int[] di:dirs) {
            int nx = x + di[0],ny = y + di[1];
            if(nx < 0 || nx >= m || ny < 0|| ny >=n) continue;
            if(res[nx][ny] || g[nx][ny] < g[x][y]) continue;
            dfs(nx,ny,res);
        }
    }
    
    
    public static void main(String[] args) {
        pacificAtlantic pacificAtlantic = new pacificAtlantic();
        int[][] heights = new int[][]{{1,2,2,3,5},
                {3,2,3,4,4},
                {2,4,5,3,1},
                {6,7,1,4,5},
                {5,1,1,2,4}};
        System.out.println(pacificAtlantic.pacificAtlantic(heights));
    }
}
